#include "hash_prime.h"

#include <deque>
#include <vector>
namespace qb {
namespace base {

////////////////////////////////////////////////////////////////////////////////
/*
prime_array,0-87由如下代码生成:
CPrimes numbers(100000000);
numbers.Filter(0.2, primes);

88-92 是原先的质数序列
*/
static int prime_array[] = {
    /*  0 */ 2,
    /*  1 */ 3,
    /*  2 */ 5,
    /*  3 */ 7,
    /*  4 */ 11,
    /*  5 */ 17,
    /*  6 */ 23,
    /*  7 */ 29,
    /*  8 */ 37,
    /*  9 */ 47,
    /* 10 */ 59,
    /* 11 */ 71,
    /* 12 */ 89,
    /* 13 */ 107,
    /* 14 */ 131,
    /* 15 */ 163,
    /* 16 */ 197,
    /* 17 */ 239,
    /* 18 */ 293,
    /* 19 */ 353,
    /* 20 */ 431,
    /* 21 */ 521,
    /* 22 */ 631,
    /* 23 */ 761,
    /* 24 */ 919,
    /* 25 */ 1103,
    /* 26 */ 1327,
    /* 27 */ 1597,
    /* 28 */ 1931,
    /* 29 */ 2333,
    /* 30 */ 2801,
    /* 31 */ 3371,
    /* 32 */ 4049,
    /* 33 */ 4861,
    /* 34 */ 5839,
    /* 35 */ 7013,
    /* 36 */ 8419,
    /* 37 */ 10103,
    /* 38 */ 12143,
    /* 39 */ 14591,
    /* 40 */ 17519,
    /* 41 */ 21023,
    /* 42 */ 25229,
    /* 43 */ 30293,
    /* 44 */ 36353,
    /* 45 */ 43627,
    /* 46 */ 52361,
    /* 47 */ 62851,
    /* 48 */ 75431,
    /* 49 */ 90523,
    /* 50 */ 108631,
    /* 51 */ 130363,
    /* 52 */ 156437,
    /* 53 */ 187751,
    /* 54 */ 225307,
    /* 55 */ 270371,
    /* 56 */ 324449,
    /* 57 */ 389357,
    /* 58 */ 467237,
    /* 59 */ 560689,
    /* 60 */ 672827,
    /* 61 */ 807403,
    /* 62 */ 968897,
    /* 63 */ 1162687,
    /* 64 */ 1395263,
    /* 65 */ 1674319,
    /* 66 */ 2009191,
    /* 67 */ 2411033,
    /* 68 */ 2893249,
    /* 69 */ 3471899,
    /* 70 */ 4166287,
    /* 71 */ 4999559,
    /* 72 */ 5999471,
    /* 73 */ 7199369,
    /* 74 */ 8639249,
    /* 75 */ 10367101,
    /* 76 */ 12440537,
    /* 77 */ 14928671,
    /* 78 */ 17914409,
    /* 79 */ 21497293,
    /* 80 */ 25796759,
    /* 81 */ 30956117,
    /* 82 */ 37147349,
    /* 83 */ 44576837,
    /* 84 */ 53492207,
    /* 85 */ 64190669,
    /* 86 */ 77028803,
    /* 87 */ 92434613,

    /* 88 */ 179669557,
    /* 89 */ 359339171,
    /* 90 */ 718678369,
    /* 91 */ 1437356741,
    /* 92 */ 2147483647,
};
#define PRIME_ARRAY_SIZE (93)
////////////////////////////////////////////////////////////////////////////////
class CPrimes : public std::vector<int> {
 public:
  CPrimes(int n) {
    n = n <= 32 ? 32 : n;
    bool* isPrimes = new bool[n + 1];
    for (int i = 2; i <= n; ++i) isPrimes[i] = true;
    isPrimes[2] = true;
    for (int j = 2; j <= n; ++j) {
      if (isPrimes[j] == true)
        for (int m = 2; j * m <= n; ++m) isPrimes[j * m] = false;
    }
    for (int i = 0; i <= n; i++) {
      if (isPrimes[i]) push_back(i);
    }
  }
  void Filter(double gap, std::vector<int>& primes) {
    int last = at(0);
    int ncount = size();
    int pmax = at(ncount - 1);

    primes.push_back(last);
    for (int i = 1; i < ncount; i++) {
      double next = last + last * gap;
      if (next >= pmax) break;
      for (int j = i; j < ncount; j++) {
        int& v = at(j);
        if (v >= next) {
          last = v;
          primes.push_back(last);
          i = j;
          break;
        }
      }
    }
  }
};
int GetHashPrimeLargerThan(int number) {
  for (int i = 0; i < PRIME_ARRAY_SIZE; i++) {
    if (prime_array[i] > number) return prime_array[i];
  }
  return 2147483647;
}
}  // namespace base
}  // namespace qb